/*
 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
 *
 *  This file is licensed to You under the Eclipse Public License (EPL);
 *  You may not use this file except in compliance with the License. You
 *  may obtain a copy of the License at
 *
 *      http://www.opensource.org/licenses/eclipse-1.0.php
 *
 *  See the COPYRIGHT.txt file distributed with this work for information
 *  regarding copyright ownership.
 */
package org.mmtk.policy;

import org.mmtk.utility.Constants;
import org.mmtk.utility.Conversions;
import org.mmtk.utility.Log;
import org.mmtk.utility.Memory;
import org.mmtk.utility.alloc.BlockAllocator;
import org.mmtk.utility.alloc.EmbeddedMetaData;
import org.mmtk.utility.heap.FreeListPageResource;
import org.mmtk.utility.heap.VMRequest;
import org.mmtk.utility.options.Options;
import org.mmtk.vm.Lock;
import org.mmtk.vm.VM;
import org.vmmagic.pragma.Inline;
import org.vmmagic.pragma.Uninterruptible;
import org.vmmagic.unboxed.Address;
import org.vmmagic.unboxed.AddressArray;
import org.vmmagic.unboxed.Extent;
import org.vmmagic.unboxed.ObjectReference;
import org.vmmagic.unboxed.Word;

/**
 * Each instance of this class corresponds to one mark-sweep *space*. Each of
 * the instance methods of this class may be called by any thread (i.e.
 * synchronization must be explicit in any instance or class method). This
 * contrasts with the MarkSweepLocal, where instances correspond to *plan*
 * instances and therefore to kernel threads. Thus unlike this class,
 * synchronization is not necessary in the instance methods of MarkSweepLocal.
 */
@Uninterruptible
public abstract class SegregatedFreeListSpace extends Space implements
		Constants {

	/****************************************************************************
	 * 
	 * Class variables
	 */
	protected static final boolean LAZY_SWEEP = true;
	private static final boolean COMPACT_SIZE_CLASSES = false;
	protected static final int MIN_CELLS = 6;
	protected static final int MAX_CELLS = 99; // (1<<(INUSE_BITS-1))-1;
	protected static final int MAX_CELL_SIZE = 8 << 10;
	public static final int MAX_FREELIST_OBJECT_BYTES = MAX_CELL_SIZE;

	// live bits etc
	private static final int OBJECT_LIVE_SHIFT = LOG_MIN_ALIGNMENT; // 4 byte
																	// resolution
	private static final int LOG_BIT_COVERAGE = OBJECT_LIVE_SHIFT;
	private static final int LOG_LIVE_COVERAGE = LOG_BIT_COVERAGE
			+ LOG_BITS_IN_BYTE;
	private static final int LIVE_BYTES_PER_REGION = 1 << (EmbeddedMetaData.LOG_BYTES_IN_REGION - LOG_LIVE_COVERAGE);
	private static final Word WORD_SHIFT_MASK = Word.one()
			.lsh(LOG_BITS_IN_WORD).minus(Extent.one());
	private static final int LOG_LIVE_WORD_STRIDE = LOG_LIVE_COVERAGE
			+ LOG_BYTES_IN_WORD;
	private static final Extent LIVE_WORD_STRIDE = Extent
			.fromIntSignExtend(1 << LOG_LIVE_WORD_STRIDE);
	private static final Word LIVE_WORD_STRIDE_MASK = LIVE_WORD_STRIDE.minus(1)
			.toWord().not();
	private static final int NET_META_DATA_BYTES_PER_REGION = BlockAllocator.META_DATA_BYTES_PER_REGION
			+ LIVE_BYTES_PER_REGION;
	protected static final int META_DATA_PAGES_PER_REGION_WITH_BITMAP = Conversions
			.bytesToPages(Extent
					.fromIntSignExtend(NET_META_DATA_BYTES_PER_REGION));
	protected static final int META_DATA_PAGES_PER_REGION_NO_BITMAP = Conversions
			.bytesToPages(Extent
					.fromIntSignExtend(BlockAllocator.META_DATA_BYTES_PER_REGION));
	private static final Extent META_DATA_OFFSET = BlockAllocator.META_DATA_EXTENT;

	// calculate worst case fragmentation very conservatively
	private static final int NEW_SIZECLASS_OVERHEAD = sizeClassCount(); // one
																		// page
																		// wasted
																		// per
																		// size
																		// class
	private static final int METADATA_OVERHEAD = META_DATA_PAGES_PER_REGION_WITH_BITMAP; // worst
																							// case
																							// scenario
	public static final float WORST_CASE_FRAGMENTATION = 1 + ((NEW_SIZECLASS_OVERHEAD + METADATA_OVERHEAD) / (float) EmbeddedMetaData.BYTES_IN_REGION);

	/****************************************************************************
	 * 
	 * Instance variables
	 */
	protected final Lock lock = VM.newLock("SegregatedFreeListGlobal");
	protected final AddressArray consumedBlockHead = AddressArray
			.create(sizeClassCount());
	protected final AddressArray flushedBlockHead = AddressArray
			.create(sizeClassCount());
	protected final AddressArray availableBlockHead = AddressArray
			.create(sizeClassCount());

	// Kathy made protected to use in subclass
	private static final boolean DEBUG = true;
	protected final int[] cellSize = new int[sizeClassCount()]; // 40 elements
	protected final byte[] blockSizeClass = new byte[sizeClassCount()];
	protected final int[] blockHeaderSize = new int[sizeClassCount()];

	/**
	 * The caller specifies the region of virtual memory to be used for this
	 * space. If this region conflicts with an existing space, then the
	 * constructor will fail.
	 * 
	 * @param name
	 *            The name of this space (used when printing error messages etc)
	 * @param pageBudget
	 *            The number of pages this space may consume before consulting
	 *            the plan
	 * @param additionalMetadata
	 *            The number of meta data bytes per region for the subclass.
	 * @param vmRequest
	 *            An object describing the virtual memory requested.
	 */
	public SegregatedFreeListSpace(String name, int pageBudget,
			int additionalMetadata, VMRequest vmRequest) {
		super(name, false, false, vmRequest);
		initSizeClasses();
		int totalMetadata = additionalMetadata;
		if (maintainSideBitmap()) {
			totalMetadata += META_DATA_PAGES_PER_REGION_WITH_BITMAP;
		} else {
			totalMetadata += META_DATA_PAGES_PER_REGION_NO_BITMAP;
		}
		if (vmRequest.isDiscontiguous()) {
			pr = new FreeListPageResource(pageBudget, this, totalMetadata);
		} else {
			pr = new FreeListPageResource(pageBudget, this, start, extent,
					totalMetadata);
		}
	}

	/**
	 * Should SegregatedFreeListSpace manage a side bitmap to keep track of live
	 * objects?
	 */
	protected abstract boolean maintainSideBitmap();

	/**
	 * Do we need to preserve free lists as we move blocks around.
	 */
	protected abstract boolean preserveFreeList();

	/****************************************************************************
	 * 
	 * Allocation
	 */

	/**
	 * Return a block to the global pool.
	 * 
	 * @param block
	 *            The block to return
	 * @param sizeClass
	 *            The size class
	 */
	public void returnConsumedBlock(Address block, int sizeClass) {
		returnBlock(block, sizeClass, Address.zero());
	}

	/**
	 * Return a block to the global pool.
	 * 
	 * @param block
	 *            The block to return
	 * @param sizeClass
	 *            The size class
	 * @param freeCell
	 *            The first free cell in the block.
	 */
	public void returnBlock(Address block, int sizeClass, Address freeCell) {
		if (VM.VERIFY_ASSERTIONS) {
			VM.assertions._assert(BlockAllocator.getNext(block).isZero());
		}
		if (preserveFreeList()) {
			setFreeList(block, freeCell);
		}
		lock.acquire();
		BlockAllocator.setNext(block, consumedBlockHead.get(sizeClass));
		consumedBlockHead.set(sizeClass, block);
		lock.release();
	}

	/**
	 * Acquire a new block from the global pool to allocate into. This method
	 * with either return a non-empty free list, or zero when allocation fails.
	 * 
	 * This method will populate the passed in free list for the given size
	 * class and return the address of the block.
	 * 
	 * @param sizeClass
	 *            The size class to allocate into
	 * @param freeList
	 *            The free list to populate
	 * @return The address of the block
	 */
	public Address getAllocationBlock(int sizeClass, AddressArray freeList) {
		lock.acquire();
		Address block;
		while (!(block = availableBlockHead.get(sizeClass)).isZero()) {
			availableBlockHead.set(sizeClass, BlockAllocator.getNext(block));
			lock.release();

			/* This block is no longer on any list */
			BlockAllocator.setNext(block, Address.zero());

			/* Can we allocate into this block? */
			Address cell = advanceToBlock(block, sizeClass);
			if (!cell.isZero()) {
				freeList.set(sizeClass, cell);
				return block;
			}

			/* Block was full */
			lock.acquire();
			BlockAllocator.setNext(block, consumedBlockHead.get(sizeClass));
			consumedBlockHead.set(sizeClass, block);
		}
		lock.release();
		return expandSizeClass(sizeClass, freeList);
	}

	/**
	 * Expand a particular size class, allocating a new block, breaking the
	 * block into cells and placing those cells on a free list for that block.
	 * The block becomes the current head for this size class and the address of
	 * the first available cell is returned.
	 * <p>
	 * 
	 * <b>This is guaranteed to return pre-zeroed cells</b>
	 * 
	 * @param sizeClass
	 *            The size class to be expanded
	 * @param freeList
	 *            The free list to populate.
	 * @return The block that was just allocated.
	 */
	@Inline
	private Address expandSizeClass(int sizeClass, AddressArray freeList) {
		Address block = BlockAllocator.alloc(this, blockSizeClass[sizeClass]);

		if (block.isZero()) {
			return Address.zero();
		}

		BlockAllocator.setNext(block, Address.zero());
		BlockAllocator.setAllClientSizeClass(block, blockSizeClass[sizeClass],
				(byte) sizeClass);

		notifyNewBlock(block, sizeClass);

		int cellExtent = cellSize[sizeClass];
		int blockSize = BlockAllocator.blockSize(blockSizeClass[sizeClass]);
		int useableBlockSize = blockSize - blockHeaderSize[sizeClass];
		Address firstCell = block.plus(blockHeaderSize[sizeClass]);
		Address sentinel = block.plus(blockSize);

		/* pre-zero the block */
		VM.memory.zero(firstCell, Extent.fromIntZeroExtend(useableBlockSize));

		/* construct the free list */
		Address nextCell;
		Address cell = firstCell;
		while ((nextCell = cell.plus(cellExtent)).LT(sentinel)) {
			cell.store(nextCell);
			cell = nextCell;
		}

		/* Populate the free list */
		freeList.set(sizeClass, firstCell);
		return block;
	}

	/****************************************************************************
	 * 
	 * Block management
	 */

	/**
	 * Initialize the size class data structures.
	 */
	private void initSizeClasses() {
		for (int sc = 0; sc < sizeClassCount(); sc++) {
			cellSize[sc] = getBaseCellSize(sc);
			for (byte blk = 0; blk < BlockAllocator.BLOCK_SIZE_CLASSES; blk++) {
				int usableBytes = BlockAllocator.blockSize(blk);
				int cells = usableBytes / cellSize[sc];
				blockSizeClass[sc] = blk;
				/*
				 * cells must start at multiple of MIN_ALIGNMENT because
				 * cellSize is also supposed to be multiple, this should do the
				 * trick:
				 */
				blockHeaderSize[sc] = BlockAllocator.blockSize(blk) - cells
						* cellSize[sc];
				if (((usableBytes < BYTES_IN_PAGE) && (cells * 2 > MAX_CELLS))
						|| ((usableBytes > (BYTES_IN_PAGE >> 1)) && (cells > MIN_CELLS)))
					break;
			}
		}
	}

	//kathy
	public void printSizeClasses() {
		Log.write("printSizeClasses\n");
		for (int i = 0; i < sizeClassCount(); i++) {
			Log.write("i=");
			Log.write(i);
			Log.write(", cellSize[i]=");
			Log.write(cellSize[i]);
			Log.write(", blockSizeClass[i]=");
			Log.write(blockSizeClass[i]);
			Log.write(", blockHeaderSize[i]=");
			Log.write(blockHeaderSize[i]);
			Log.write("\n");
			Log.flush();
		}
	}

	/**
	 * Get the size class for a given number of bytes.
	 * 
	 * We use size classes based on a worst case internal fragmentation loss
	 * target of 1/8. In fact, across sizes from 8 bytes to 512 the average
	 * worst case loss is 13.3%, giving an expected loss (assuming uniform
	 * distribution) of about 7%. We avoid using the Lea class sizes because
	 * they were so numerous and therefore liable to lead to excessive
	 * inter-class-size fragmentation.
	 * <p>
	 * 
	 * This method may segregate arrays and scalars (currently it does not).
	 * <p>
	 * 
	 * This method should be more intelligent and take alignment requests into
	 * consideration. The issue with this is that the block header which can be
	 * varied by subclasses can change the alignment of the cells.
	 * <p>
	 * 
	 * @param bytes
	 *            The number of bytes required to accommodate the object to be
	 *            allocated.
	 * @return The size class capable of accommodating the allocation request.
	 */
	@Inline
	public final int getSizeClass(int bytes) {
		if (VM.VERIFY_ASSERTIONS) {
			// Log.write("getSizeClass, bytes=");
			// Log.write(bytes);
			// Log.write(", MAX_CELL_SIZE= ");
			// Log.write(MAX_CELL_SIZE);
			VM.assertions._assert((bytes > 0) && (bytes <= MAX_CELL_SIZE));
		}

		int sz1 = bytes - 1;

		if (BYTES_IN_ADDRESS == 4) { // 32-bit
			if (COMPACT_SIZE_CLASSES)
				return ((sz1 <= 31) ? (sz1 >> 2) : // 4 bytes apart
						(sz1 <= 63) ? 4 + (sz1 >> 3) : // 8 bytes apart
								(sz1 <= 95) ? 8 + (sz1 >> 4) : // 16 bytes apart
										(sz1 <= 223) ? 14 + (sz1 >> 6) : // 64
																			// bytes
																			// apart
												(sz1 <= 734) ? 17 + (sz1 >> 8) : // 256
																					// bytes
																					// apart
														20 + (sz1 >> 10)); // 1024
																			// bytes
																			// apart
			else
				return ((sz1 <= 63) ? (sz1 >> 2) : // 4 bytes apart
						(sz1 <= 127) ? 12 + (sz1 >> 4) : // 16 bytes apart
								(sz1 <= 255) ? 16 + (sz1 >> 5) : // 32 bytes
																	// apart
										(sz1 <= 511) ? 20 + (sz1 >> 6) : // 64
																			// bytes
																			// apart
												(sz1 <= 2047) ? 26 + (sz1 >> 8)
														: // 256 bytes apart
														32 + (sz1 >> 10)); // 1024
																			// bytes
																			// apart
		} else { // 64-bit
			if (COMPACT_SIZE_CLASSES)
				return ((sz1 <= 95) ? (sz1 >> 3) : // 8 bytes apart
						(sz1 <= 127) ? 6 + (sz1 >> 4) : // 16 bytes apart
								(sz1 <= 191) ? 10 + (sz1 >> 5) : // 32 bytes
																	// apart
										(sz1 <= 383) ? 13 + (sz1 >> 6) : // 64
																			// bytes
																			// apart
												(sz1 <= 511) ? 16 + (sz1 >> 7) : // 128
																					// bytes
																					// apart
														(sz1 <= 1023) ? 19 + (sz1 >> 9)
																: // 512 bytes
																	// apart
																20 + (sz1 >> 10)); // 1024
																					// bytes
																					// apart
			else
				return ((sz1 <= 111) ? (sz1 >> 3) : // 8 bytes apart
						(sz1 <= 223) ? 7 + (sz1 >> 4) : // 16 bytes apart
								(sz1 <= 319) ? 14 + (sz1 >> 5) : // 32 bytes
																	// apart
										(sz1 <= 575) ? 19 + (sz1 >> 6) : // 64
																			// bytes
																			// apart
												(sz1 <= 2047) ? 26 + (sz1 >> 8)
														: // 256 bytes apart
														32 + (sz1 >> 10)); // 1024
																			// bytes
																			// apart
		}
	}

	/**
	 * Return the size of a basic cell (i.e. not including any cell header) for
	 * a given size class.
	 * 
	 * @param sc
	 *            The size class in question
	 * @return The size of a basic cell (i.e. not including any cell header).
	 */
	@Inline
	public final int getBaseCellSize(int sc) {
		if (VM.VERIFY_ASSERTIONS)
			VM.assertions._assert((sc >= 0) && (sc < sizeClassCount()));

		if (BYTES_IN_ADDRESS == 4) { // 32-bit
			if (COMPACT_SIZE_CLASSES)
				return ((sc < 8) ? (sc + 1) << 2 : (sc < 12) ? (sc - 3) << 3
						: (sc < 16) ? (sc - 7) << 4
								: (sc < 18) ? (sc - 13) << 6
										: (sc < 21) ? (sc - 16) << 8
												: (sc - 19) << 10);
			else
				return ((sc < 16) ? (sc + 1) << 2 : (sc < 20) ? (sc - 11) << 4
						: (sc < 24) ? (sc - 15) << 5
								: (sc < 28) ? (sc - 19) << 6
										: (sc < 34) ? (sc - 25) << 8
												: (sc - 31) << 10);
		} else { // 64-bit
			if (COMPACT_SIZE_CLASSES)
				return ((sc < 12) ? (sc + 1) << 3 : (sc < 14) ? (sc - 5) << 4
						: (sc < 16) ? (sc - 9) << 5
								: (sc < 19) ? (sc - 12) << 6
										: (sc < 20) ? (sc - 15) << 7
												: (sc < 21) ? (sc - 18) << 9
														: (sc - 19) << 10);
			else
				return ((sc < 14) ? (sc + 1) << 3 : (sc < 21) ? (sc - 6) << 4
						: (sc < 24) ? (sc - 13) << 5
								: (sc < 28) ? (sc - 18) << 6
										: (sc < 34) ? (sc - 25) << 8
												: (sc - 31) << 10);
		}
	}

	/**
	 * The number of distinct size classes.
	 */
	@Inline
	public static int sizeClassCount() {
		return (COMPACT_SIZE_CLASSES) ? 28 : 40;
	}

	/****************************************************************************
	 * 
	 * Preserving (saving & restoring) free lists
	 */

	/**
	 * Prepare a block for allocation, returning a free list into the block.
	 * 
	 * @param block
	 *            The new block
	 * @param sizeClass
	 *            The block's sizeclass.
	 */
	protected abstract Address advanceToBlock(Address block, int sizeClass);

	/**
	 * Notify that a new block has been installed.
	 * 
	 * @param block
	 *            The new block
	 * @param sizeClass
	 *            The block's sizeclass.
	 */
	protected void notifyNewBlock(Address block, int sizeClass) {
	}

	/**
	 * Should the sweep reclaim the cell containing this object. Is this object
	 * live. This is only used when maintainSideBitmap is false.
	 * 
	 * @param object
	 *            The object to query
	 * @return True if the cell should be reclaimed
	 */
	protected boolean reclaimCellForObject(ObjectReference object) {
		VM.assertions
				.fail("Must implement reclaimCellForObject if not maintaining side bitmap");
		return false;
	}

	/****************************************************************************
	 * 
	 * Metadata manipulation
	 */

	/**
	 * In the case where free lists associated with each block are preserved,
	 * get the free list for a given block.
	 * 
	 * @param block
	 *            The block whose free list is to be found
	 * @return The free list for this block
	 */
	@Inline
	protected final Address getFreeList(Address block) {
		if (VM.VERIFY_ASSERTIONS)
			VM.assertions._assert(preserveFreeList());
		return BlockAllocator.getFreeListMeta(block);
	}

	/**
	 * In the case where free lists associated with each block are preserved,
	 * set the free list for a given block.
	 * 
	 * @param block
	 *            The block whose free list is to be found
	 * @param cell
	 *            The head of the free list (i.e. the first cell in the free
	 *            list).
	 */
	@Inline
	protected final void setFreeList(Address block, Address cell) {
		if (VM.VERIFY_ASSERTIONS)
			VM.assertions._assert(preserveFreeList());
		BlockAllocator.setFreeListMeta(block, cell);
	}

	/****************************************************************************
	 * 
	 * Collection
	 */

	/**
	 * Clear all block marks for this space. This method is important when it is
	 * desirable to do partial collections, which man mean that block marks need
	 * to be explicitly cleared when necessary.
	 */
	protected final void clearAllBlockMarks() {
		if (VM.VERIFY_ASSERTIONS)
			VM.assertions._assert(!maintainSideBitmap());
		for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
			Extent blockSize = Extent.fromIntSignExtend(BlockAllocator
					.blockSize(blockSizeClass[sizeClass]));
			/* Flushed blocks */
			Address block = flushedBlockHead.get(sizeClass);
			while (!block.isZero()) {
				Address next = BlockAllocator.getNext(block);
				clearBlockMark(block, blockSize);
				block = next;
			}
			/* Available blocks */
			block = consumedBlockHead.get(sizeClass);
			while (!block.isZero()) {
				Address next = BlockAllocator.getNext(block);
				clearBlockMark(block, blockSize);
				block = next;
			}
		}
	}

	/**
	 * Sweep all blocks for free objects.
	 * 
	 * @param clearMarks
	 *            should we clear block mark bits as we process.
	 */
	protected final void sweepConsumedBlocks(boolean clearMarks) {
		if (Options.verbose.getValue() >= 3) {
			Log.prependThreadId();
			Log.write("sweepConsumedBlocks entered, clearMarks=");
			Log.writeln(clearMarks);
		}

		for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
			Extent blockSize = Extent.fromIntSignExtend(BlockAllocator
					.blockSize(blockSizeClass[sizeClass]));
			Address availableHead = Address.zero();

			/* Flushed blocks */
			Address block = flushedBlockHead.get(sizeClass);
			flushedBlockHead.set(sizeClass, Address.zero());
			while (!block.isZero()) {
				Address next = BlockAllocator.getNext(block);
				availableHead = sweepBlock(block, sizeClass, blockSize,
						availableHead, clearMarks);
				block = next;
			}

			/* Consumed blocks */
			block = consumedBlockHead.get(sizeClass);
			consumedBlockHead.set(sizeClass, Address.zero());
			while (!block.isZero()) {
				Address next = BlockAllocator.getNext(block);
				availableHead = sweepBlock(block, sizeClass, blockSize,
						availableHead, clearMarks);
				block = next;
			}

			/* Make blocks available */
			availableBlockHead.set(sizeClass, availableHead);
		}
	}

	// Kathy
	protected final void sweepConsumedBlocks(boolean clearMarks, Sweeper sweeper) {
		if (DEBUG) {
			Log.prependThreadId();
			Log.write("SegregatedFreeListSpace.sweepConsumedBlocks entered, clearMarks=");
			Log.writeln(clearMarks);
			Log.flush();
		}

		for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
			Extent blockSize = Extent.fromIntSignExtend(BlockAllocator
					.blockSize(blockSizeClass[sizeClass]));
			Address availableHead = Address.zero();
			Address block;

			if (DEBUG) {
				Log.prependThreadId();
				Log.write("SegregatedFreeListSpace.sweepConsumedBlocks, sizeClass=");
				Log.write(sizeClass);
				Log.write(", blockSize=");
				Log.writeln(blockSize);
				Log.flush();
			}
			
			block = availableBlockHead.get(sizeClass);	
			if(!block.isZero()) {
				int availableBlocks = 0;
				if (DEBUG) {
					Log.prependThreadId();
					Log.write("SegregatedFreeListSpace.sweepConsumedBlocks, sweeping availableBlocks ");
					Log.writeln(block);
					Log.flush();
				}
				while (!block.isZero()) {
					availableBlocks++;
					Address next = BlockAllocator.getNext(block);
					availableHead = sweepBlock(sweeper, block, sizeClass,blockSize, availableHead, clearMarks);
					block = next;
				}
				if (DEBUG) {
					Log.prependThreadId();
					Log.write("SegregatedFreeListSpace.sweepConsumedBlocks, availableBlocks=");
					Log.writeln(availableBlocks);
					Log.flush();
				}
			}
						
			block = flushedBlockHead.get(sizeClass);
			if(!block.isZero()) {
				flushedBlockHead.set(sizeClass, Address.zero());
				int flushedBlocks = 0;
				if (DEBUG) {
					Log.prependThreadId();
					Log.write("SegregatedFreeListSpace.sweepConsumedBlocks, sweeping flushedBlocks ");
					Log.writeln(block);
					Log.flush();
				}
				while (!block.isZero()) {
					flushedBlocks++;
					Address next = BlockAllocator.getNext(block);
					availableHead = sweepBlock(sweeper, block, sizeClass,
							blockSize, availableHead, clearMarks);
					block = next;
				}
				if (DEBUG) {
					Log.prependThreadId();
					Log.write("SegregatedFreeListSpace.sweepConsumedBlocks, flushedBlocks=");
					Log.writeln(flushedBlocks);
					Log.flush();
				}
			}
			
			block = consumedBlockHead.get(sizeClass);
			if(!block.isZero()) {
				int consumedBlocks = 0;	
				consumedBlockHead.set(sizeClass, Address.zero());
				if (DEBUG) {
					Log.prependThreadId();
					Log.write("SegregatedFreeListSpace.sweepConsumedBlocks, sweeping consumedBlocks ");
					Log.writeln(block);
					Log.flush();
				}
				while (!block.isZero()) {
					consumedBlocks++;
					Address next = BlockAllocator.getNext(block);
					availableHead = sweepBlock(sweeper, block, sizeClass,
							blockSize, availableHead, clearMarks);
					block = next;
				}
				if (DEBUG) {
					Log.prependThreadId();
					Log.write("SegregatedFreeListSpace.sweepConsumedBlocks, consumedBlocks=");
					Log.writeln(consumedBlocks);
					Log.flush();
				}
			}

			/* Make blocks available */
			availableBlockHead.set(sizeClass, availableHead);
		}
	}

	/**
	 * Sweep a block, freeing it and adding to the list given by availableHead
	 * if it contains no free objects.
	 * 
	 * @param clearMarks
	 *            should we clear block mark bits as we process.
	 */
	protected final Address sweepBlock(Address block, int sizeClass,
			Extent blockSize, Address availableHead, boolean clearMarks) {
		boolean liveBlock = containsLiveCell(block, blockSize, clearMarks);
		if (!liveBlock) {
			BlockAllocator.setNext(block, Address.zero());
			BlockAllocator.free(this, block);
		} else {
			BlockAllocator.setNext(block, availableHead);
			availableHead = block;
			if (!LAZY_SWEEP) {
				setFreeList(block, makeFreeList(block, sizeClass));
			}
		}
		return availableHead;
	}

	//kathy
	protected final Address sweepBlock(Sweeper sweeper, Address block,
			int sizeClass, Extent blockSize, Address availableHead,
			boolean clearMarks) {
		boolean liveBlock = containsLiveCell(sweeper, sizeClass, block,
				blockSize, clearMarks);
		if (DEBUG) {
			Log.prependThreadId();
			Log.write("SegregatedFreeListSpace.sweepBlock, block=");
			Log.write(block);
			Log.write(", liveBlock=");
			Log.writeln(liveBlock);
			Log.flush();
		}
		if (!liveBlock) {
			BlockAllocator.setNext(block, Address.zero());
			BlockAllocator.free(this, block);
		} else {
			BlockAllocator.setNext(block, availableHead);
			availableHead = block;
			if (!LAZY_SWEEP) {
				setFreeList(block, makeFreeList(block, sizeClass));
			}
		}
		return availableHead;
	}

	/**
	 * Eagerly consume all remaining blocks.
	 */
	protected final void consumeBlocks() {
		for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
			while (!getAllocationBlock(sizeClass, null).isZero())
				;
		}
	}

	/**
	 * Flush all the allocation blocks to the consumed list.
	 */
	protected final void flushAvailableBlocks() {
		for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
			flushedBlockHead.set(sizeClass, availableBlockHead.get(sizeClass));
			availableBlockHead.set(sizeClass, Address.zero());
		}
	}

	/**
	 * Does this block contain any live cells.
	 * 
	 * @param block
	 *            The block
	 * @param blockSize
	 *            The size of the block
	 * @param clearMarks
	 *            should we clear block mark bits as we process.
	 * @return True if any cells in the block are live
	 */
	@Inline
	protected boolean containsLiveCell(Address block, Extent blockSize,
			boolean clearMarks) {
		if (maintainSideBitmap()) {
			if (VM.VERIFY_ASSERTIONS)
				VM.assertions._assert(alignToLiveStride(block).EQ(block));
			Address cursor = getLiveWordAddress(block);
			Address sentinel = getLiveWordAddress(block
					.plus(blockSize.minus(1)));
			while (cursor.LE(sentinel)) {
				Word live = cursor.loadWord();
				if (!live.isZero()) {
					return true;
				}
				cursor = cursor.plus(BYTES_IN_WORD);
			}
			return false;
		} else {
			boolean live = false;
			Address cursor = block;
			while (cursor.LT(block.plus(blockSize))) {
				live |= BlockAllocator.checkBlockMeta(cursor);
				if (clearMarks)
					BlockAllocator.clearBlockMeta(cursor);
				cursor = cursor.plus(1 << BlockAllocator.LOG_MIN_BLOCK);
			}
			return live;
		}
	}

	//kathy
	@Inline
	protected boolean containsLiveCell(Sweeper sweeper, int sizeClass,
			Address block, Extent blockSize, boolean clearMarks) {
		if (maintainSideBitmap()) {
			if (VM.VERIFY_ASSERTIONS)
				VM.assertions._assert(alignToLiveStride(block).EQ(block));
			Address cursor = getLiveWordAddress(block);
			Address sentinel = getLiveWordAddress(block
					.plus(blockSize.minus(1)));
			while (cursor.LE(sentinel)) {
				Word live = cursor.loadWord();
				if (!live.isZero()) {
					return true;
				}
				cursor = cursor.plus(BYTES_IN_WORD);
			}
			return false;
		} else {
			boolean live = false;
			int times = 0;
			Address cursor = block;
			while (cursor.LT(block.plus(blockSize))) {
				times++;
				boolean blockMetaSet = BlockAllocator.checkBlockMeta(cursor);
				if (DEBUG) {
					Log.prependThreadId();
					Log.write("SegregatedFreeListSpace.containsLiveCell, times=");
					Log.write(times);
					Log.write(", cursor=");
					Log.write(cursor);
					Log.write(", blockMetaSet=");
					Log.writeln(blockMetaSet);
					Log.flush();
				}
				if(sweeper != null) {
					sweepCellsInBlock(sweeper, block, sizeClass);
				}
				live |= blockMetaSet;
				if (clearMarks) {
					BlockAllocator.clearBlockMeta(cursor);
				}
				cursor = cursor.plus(1 << BlockAllocator.LOG_MIN_BLOCK);
			}
			return live;
		}
	}

	//kathy
	private void sweepCellsInBlock(Sweeper sweeper, Address block, int sizeClass) {
		Extent blockSize = Extent.fromIntSignExtend(BlockAllocator
				.blockSize(blockSizeClass[sizeClass]));
		Address cursor = block.plus(blockHeaderSize[sizeClass]);
		Address end = block.plus(blockSize);
		Extent cellExtent = Extent.fromIntSignExtend(cellSize[sizeClass]);
		int cells = 0;
		ObjectReference current;
		if (DEBUG && Options.scaleDebug.getValue() > 3) {
			Log.prependThreadId();
			Log.write("SegregatedFreeListSpace.sweepCellsInBlock, blockSize=");
			Log.write(blockSize);
			Log.write(", cursor=");
			Log.write(cursor);
			Log.write(", end=");
			Log.write(end);
			Log.write(", cellExtent=");
			Log.writeln(cellExtent);
			Log.flush();
		}
		while (cursor.LT(end)) {
			if (DEBUG && Options.scaleDebug.getValue() > 3) {
				Log.prependThreadId();
				Log.write("SegregatedFreeListSpace.sweepCellsInBlock, cursor=");
				Log.write(cursor);
				Log.flush();
			}
			cells++;
			//current = VM.objectModel.getObjectFromStartAddress(cursor);
			current = cursor.plus(16).toObjectReference();
			if (DEBUG && Options.scaleDebug.getValue() > 3) {
				Log.write(", current=");
				Log.writeln(current);
				Log.flush();
			}
			sweeper.sweepCell(current);
			cursor = cursor.plus(cellExtent);
		}
		if (DEBUG && Options.scaleDebug.getValue() > 3) {
			Log.prependThreadId();
			Log.write("SegregatedFreeListSpace.sweepCellsInBlock, cells=");
			Log.writeln(cells);
			Log.flush();
		}
	}

	/**
	 * Clear block marks for a block
	 * 
	 * @param block
	 *            The block
	 * @param blockSize
	 *            The size of the block
	 */
	@Inline
	protected void clearBlockMark(Address block, Extent blockSize) {
		if (VM.VERIFY_ASSERTIONS)
			VM.assertions._assert(!maintainSideBitmap());
		Address cursor = block;
		while (cursor.LT(block.plus(blockSize))) {
			BlockAllocator.clearBlockMeta(cursor);
			cursor = cursor.plus(1 << BlockAllocator.LOG_MIN_BLOCK);
		}
	}

	/**
	 * In the cell containing this object live?
	 * 
	 * @param object
	 *            The object
	 * @return True if the cell is live
	 */
	@Inline
	protected boolean isCellLive(ObjectReference object) {
		/* Must override if not using the side bitmap */
		if (VM.VERIFY_ASSERTIONS)
			VM.assertions._assert(maintainSideBitmap());
		return liveBitSet(object);
	}

	/**
	 * Use the live bits for a block to infer free cells and thus construct a
	 * free list for the block.
	 * 
	 * @param block
	 *            The block to be processed
	 * @param sizeClass
	 *            The size class for the block
	 * @return The head of the new free list
	 */
	@Inline
	protected final Address makeFreeList(Address block, int sizeClass) {
		Extent blockSize = Extent.fromIntSignExtend(BlockAllocator
				.blockSize(blockSizeClass[sizeClass]));
		Address cursor = block.plus(blockHeaderSize[sizeClass]);
		Address lastFree = Address.zero();
		Address firstFree = Address.zero();
		Address end = block.plus(blockSize);
		Extent cellExtent = Extent.fromIntSignExtend(cellSize[sizeClass]);
		while (cursor.LT(end)) {
			ObjectReference current = VM.objectModel
					.getObjectFromStartAddress(cursor);
			boolean free = true;
			if (!current.isNull()) {
				free = !isCellLive(current);
			}
			if (free) {
				if (firstFree.isZero()) {
					firstFree = cursor;
				} else {
					lastFree.store(cursor);
				}
				Memory.zeroSmall(cursor, cellExtent);
				lastFree = cursor;
			}
			cursor = cursor.plus(cellExtent);
		}
		return firstFree;
	}

	/**
	 * Sweep all blocks for free objects.
	 */
	public void sweepCells(Sweeper sweeper) {
		for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
			Address availableHead = Address.zero();
			/* Flushed blocks */
			Address block = flushedBlockHead.get(sizeClass);
			flushedBlockHead.set(sizeClass, Address.zero());
			while (!block.isZero()) {
				Address next = BlockAllocator.getNext(block);
				availableHead = sweepCells(sweeper, block, sizeClass,
						availableHead);
				block = next;
			}
			/* Consumed blocks */
			block = consumedBlockHead.get(sizeClass);
			consumedBlockHead.set(sizeClass, Address.zero());
			while (!block.isZero()) {
				Address next = BlockAllocator.getNext(block);
				availableHead = sweepCells(sweeper, block, sizeClass,
						availableHead);
				block = next;
			}
			/* Make blocks available */
			availableBlockHead.set(sizeClass, availableHead);
		}
	}

	/**
	 * Sweep a block, freeing it and adding to the list given by availableHead
	 * if it contains no free objects.
	 */
	private Address sweepCells(Sweeper sweeper, Address block, int sizeClass,
			Address availableHead) {
		boolean liveBlock = sweepCells(sweeper, block, sizeClass);
		if (!liveBlock) {
			BlockAllocator.setNext(block, Address.zero());
			BlockAllocator.free(this, block);
		} else {
			BlockAllocator.setNext(block, availableHead);
			availableHead = block;
		}
		return availableHead;
	}

	/**
	 * Sweep a block, freeing it and making it available if any live cells were
	 * found. if it contains no free objects.
	 * 
	 * This is designed to be called in parallel by multiple collector threads.
	 */
	public void parallelSweepCells(Sweeper sweeper) {
		for (int sizeClass = 0; sizeClass < sizeClassCount(); sizeClass++) {
			Address block;
			while (!(block = getSweepBlock(sizeClass)).isZero()) {
				boolean liveBlock = sweepCells(sweeper, block, sizeClass);
				if (!liveBlock) {
					BlockAllocator.setNext(block, Address.zero());
					BlockAllocator.free(this, block);
				} else {
					lock.acquire();
					BlockAllocator.setNext(block, availableBlockHead
							.get(sizeClass));
					availableBlockHead.set(sizeClass, block);
					lock.release();
				}
			}
		}
	}

	/**
	 * Get a block for a parallel sweep.
	 * 
	 * @param sizeClass
	 *            The size class of the block to sweep.
	 * @return The block or zero if no blocks remain to be swept.
	 */
	private Address getSweepBlock(int sizeClass) {
		lock.acquire();
		Address block;

		/* Flushed blocks */
		block = flushedBlockHead.get(sizeClass);
		if (!block.isZero()) {
			flushedBlockHead.set(sizeClass, BlockAllocator.getNext(block));
			lock.release();
			BlockAllocator.setNext(block, Address.zero());
			return block;
		}

		/* Consumed blocks */
		block = consumedBlockHead.get(sizeClass);
		if (!block.isZero()) {
			flushedBlockHead.set(sizeClass, BlockAllocator.getNext(block));
			lock.release();
			BlockAllocator.setNext(block, Address.zero());
			return block;
		}

		/* All swept! */
		lock.release();
		return Address.zero();
	}

	/**
	 * Does this block contain any live cells?
	 */
	@Inline
	public boolean sweepCells(Sweeper sweeper, Address block, int sizeClass) {
		Extent blockSize = Extent.fromIntSignExtend(BlockAllocator
				.blockSize(blockSizeClass[sizeClass]));
		Address cursor = block.plus(blockHeaderSize[sizeClass]);
		Address end = block.plus(blockSize);
		Extent cellExtent = Extent.fromIntSignExtend(cellSize[sizeClass]);
		boolean containsLive = false;
		while (cursor.LT(end)) {
			ObjectReference current = VM.objectModel
					.getObjectFromStartAddress(cursor);
			boolean free = true;
			if (!current.isNull()) {
				free = !liveBitSet(current);
				if (!free) {
					free = sweeper.sweepCell(current);
					if (free)
						unsyncClearLiveBit(current);
				}
			}
			if (!free) {
				containsLive = true;
			}
			cursor = cursor.plus(cellExtent);
		}
		return containsLive;
	}

	/**
	 * A callback used to perform sweeping of a free list space.
	 */
	@Uninterruptible
	public abstract static class Sweeper {
		public void start() {
			
		}
		public abstract boolean sweepCell(ObjectReference object);
		public void end() {
			
		}
	}
	
	@Uninterruptible
	public abstract static class Scanner {
		public abstract void release();
		public abstract void start(int prevMarkColor, int scan);
		public abstract boolean scanCell(ObjectReference object, int color);
		public abstract void end();
	}

	/****************************************************************************
	 * 
	 * Live bit manipulation
	 */

	/**
	 * Atomically set the live bit for a given object
	 * 
	 * @param object
	 *            The object whose live bit is to be set.
	 * @return True if the bit was changed to true.
	 */
	@Inline
	public static boolean testAndSetLiveBit(ObjectReference object) {
		return updateLiveBit(VM.objectModel.objectStartRef(object), true, true);
	}

	/**
	 * Set the live bit for the block containing the given object
	 * 
	 * @param object
	 *            The object whose blocks liveness is to be set.
	 */
	@Inline
	protected static void markBlock(ObjectReference object) {
		BlockAllocator.markBlockMeta(object);
	}

	/**
	 * Set the live bit for the given block.
	 * 
	 * @param block
	 *            The block whose liveness is to be set.
	 */
	@Inline
	protected static void markBlock(Address block) {
		BlockAllocator.markBlockMeta(block);
	}

	/**
	 * Set the live bit for a given object, without using synchronization
	 * primitives---must only be used when contention for live bit is strictly
	 * not possible
	 * 
	 * @param object
	 *            The object whose live bit is to be set.
	 */
	@Inline
	public static boolean unsyncSetLiveBit(ObjectReference object) {
		return updateLiveBit(VM.objectModel.refToAddress(object), true, false);
	}

	/**
	 * Set the live bit for a given address
	 * 
	 * @param address
	 *            The address whose live bit is to be set.
	 * @param set
	 *            True if the bit is to be set, as opposed to cleared
	 * @param atomic
	 *            True if we want to perform this operation atomically
	 */
	@Inline
	private static boolean updateLiveBit(Address address, boolean set,
			boolean atomic) {
		Word oldValue, newValue;
		Address liveWord = getLiveWordAddress(address);
		Word mask = getMask(address, true);
		if (atomic) {
			do {
				oldValue = liveWord.prepareWord();
				newValue = (set) ? oldValue.or(mask) : oldValue.and(mask.not());
			} while (!liveWord.attempt(oldValue, newValue));
		} else {
			oldValue = liveWord.loadWord();
			liveWord.store(set ? oldValue.or(mask) : oldValue.and(mask.not()));
		}
		return oldValue.and(mask).NE(mask);
	}

	/**
	 * Test the live bit for a given object
	 * 
	 * @param object
	 *            The object whose live bit is to be set.
	 */
	@Inline
	protected static boolean liveBitSet(ObjectReference object) {
		return liveBitSet(VM.objectModel.refToAddress(object));
	}

	/**
	 * Set the live bit for a given address
	 * 
	 * @param address
	 *            The address whose live bit is to be set.
	 * @return true if this operation changed the state of the live bit.
	 */
	@Inline
	protected static boolean liveBitSet(Address address) {
		Address liveWord = getLiveWordAddress(address);
		Word mask = getMask(address, true);
		Word value = liveWord.loadWord();
		return value.and(mask).EQ(mask);
	}

	/**
	 * Clear the live bit for a given object
	 * 
	 * @param object
	 *            The object whose live bit is to be cleared.
	 */
	@Inline
	protected static void clearLiveBit(ObjectReference object) {
		clearLiveBit(VM.objectModel.refToAddress(object));
	}

	/**
	 * Clear the live bit for a given address
	 * 
	 * @param address
	 *            The address whose live bit is to be cleared.
	 */
	@Inline
	protected static void clearLiveBit(Address address) {
		updateLiveBit(address, false, true);
	}

	/**
	 * Clear the live bit for a given object
	 * 
	 * @param object
	 *            The object whose live bit is to be cleared.
	 */
	@Inline
	protected static void unsyncClearLiveBit(ObjectReference object) {
		unsyncClearLiveBit(VM.objectModel.refToAddress(object));
	}

	/**
	 * Clear the live bit for a given address
	 * 
	 * @param address
	 *            The address whose live bit is to be cleared.
	 */
	@Inline
	protected static void unsyncClearLiveBit(Address address) {
		updateLiveBit(address, false, false);
	}

	/**
	 * Clear all live bits for a block
	 */
	protected void clearLiveBits(Address block, int sizeClass) {
		int blockSize = BlockAllocator.blockSize(blockSizeClass[sizeClass]);
		Address cursor = getLiveWordAddress(block);
		Address sentinel = getLiveWordAddress(block.plus(blockSize - 1));
		while (cursor.LE(sentinel)) {
			cursor.store(Word.zero());
			cursor = cursor.plus(BYTES_IN_WORD);
		}
	}

	/**
	 * Clear all live bits
	 */
	protected static void zeroLiveBits(Address start, Address end) {
		Extent bytes = Extent
				.fromIntSignExtend(EmbeddedMetaData.BYTES_IN_REGION >> LOG_LIVE_COVERAGE);
		while (start.LT(end)) {
			Address metadata = EmbeddedMetaData.getMetaDataBase(start).plus(
					META_DATA_OFFSET);
			VM.memory.zero(metadata, bytes);
			start = start.plus(EmbeddedMetaData.BYTES_IN_REGION);
		}
	}

	/**
	 * Align an address so that it corresponds to a live word boundary. In other
	 * words, if the live bit for the given address is not the zeroth bit of a
	 * live word, round the address down such that it does.
	 * 
	 * @param address
	 *            The address to be aligned to a live word
	 * @return The given address, aligned down so that it corresponds to an
	 *         address on a live word boundary.
	 */
	private static Address alignToLiveStride(Address address) {
		return address.toWord().and(LIVE_WORD_STRIDE_MASK).toAddress();
	}

	/**
	 * Given an address, produce a bit mask for the live table
	 * 
	 * @param address
	 *            The address whose live bit mask is to be established
	 * @param set
	 *            True if we want the mask for <i>setting</i> the bit, false if
	 *            we want the mask for <i>clearing</i> the bit.
	 * @return The appropriate bit mask for object for the live table for.
	 */
	@Inline
	private static Word getMask(Address address, boolean set) {
		int shift = address.toWord().rshl(OBJECT_LIVE_SHIFT).and(
				WORD_SHIFT_MASK).toInt();
		Word rtn = Word.one().lsh(shift);
		return (set) ? rtn : rtn.not();
	}

	/**
	 * Given an address, return the address of the live word for that address.
	 * 
	 * @param address
	 *            The address whose live word address is to be returned
	 * @return The address of the live word for this object
	 */
	@Inline
	private static Address getLiveWordAddress(Address address) {
		Address rtn = EmbeddedMetaData.getMetaDataBase(address);
		return rtn.plus(META_DATA_OFFSET).plus(
				EmbeddedMetaData.getMetaDataOffset(address, LOG_LIVE_COVERAGE,
						LOG_BYTES_IN_WORD));
	}
}
